package ljl.alg.jianzhioffer.round2;

import java.util.*;

public class _38_permutation {
    
    /**
     * 公式只记住了：
     * 1. 退出条件
     * 2. 干活
     * 3. 恢复状态
     *
     * 我记着有四步？怎么只写出来三步。
     *
     * 他这个有重复的，得改用 set
     *
     * */
    Set<String> res = new HashSet<>();
    public String[] permutation2(String s) {
        helper(s.toCharArray(), 0, s.length());
        return res.toArray(new String[0]);
    }
    void helper(char[] arr, int i, int len) {
        if (i == len) {
            res.add(new String(arr));
            return;
        }
        for (int j = i; j < len; j++) {
            // i 这个位置的数，可以是 i 后面所有数，所以交换一发
            swap(arr, i, j);
            helper(arr, i + 1, len);
            swap(arr, i, j);
        }
    }
    void swap(char[] arr, int i, int j) {
        if (i != j) {
            char t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
    
    /**
     * 路飞是怎么去重的
     * 比我快点确实
     * */
    List<String> list = new ArrayList<>();
    char[] arr;
    public String[] permutation(String s) {
        arr = s.toCharArray();
        dfs(0);
        return list.toArray(new String[0]);
    }
    void dfs(int x) {
        if (x == arr.length) {
            list.add(String.valueOf(arr));
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = x; i < arr.length; i++) {
            if (!set.add(arr[i])) continue;
            swap(arr, x, i);
            dfs(x + 1);
            swap(arr, x, i);
        }
    }
    
    /**
     * 这个和其它的思路不一样
     * 是搞了个 visited 数组，表示每个位置
     * 然后每次循环都要判断这个 visited，如果访问过，或没访问过但是和当前一样，都跳过
     *
     * 这不合理啊，为啥要判断上一个字符没访问过，且最近两个字符一样
     * visited[i - 1] && arr[i] == arr[i - 1]
     * */
    class test {
        List<String> list = new ArrayList<>();
        boolean[] visited;
        char[] arr;
        StringBuilder sb = new StringBuilder();
        public String[] permutation(String s) {
            arr = s.toCharArray();
            Arrays.sort(arr);
            visited = new boolean[arr.length];
            dfs(0);
            return list.toArray(new String[0]);
        }
        void dfs(int x) {
            if (x == arr.length) {
                list.add(sb.toString());
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                // 这个 !visited[i - 1] && arr[i - 1] == arr[i]
                // 对于当前这个位置 x，从 0 开始试能不能放第 i 个元素
                // 正常是从前往后放的，如果前一个没放，说明是在回溯
                // 是在回溯，说明之前放过了
                // 之前放过，还和现在一样，说明不能放了
                // 不能放了，所以 continue
                // 非常的绕！
                if (visited[i] || i > 0 && !visited[i - 1] && arr[i - 1] == arr[i]) continue;
                visited[i] = true;
                sb.append(arr[i]);
                dfs(x + 1);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
}
